package com.sheng.leetcode.year2022.month04.day27;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author liusheng
 * @date 2022/04/27
 *
 * 417. 太平洋大西洋水流问题
 *
 * 有一个 m × n 的矩形岛屿，与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和上边界，
 * 而 “大西洋” 处于大陆的右边界和下边界。
 * 这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights ，
 * heights[r][c] 表示坐标 (r, c) 上单元格 高于海平面的高度 。
 * 岛上雨水较多，如果相邻单元格的高度 小于或等于 当前单元格的高度，
 * 雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。
 * 返回 网格坐标 result 的 2D列表 ，其中 result[i] = [ri, ci] 表示
 * 雨水可以从单元格 (ri, ci) 流向 太平洋和大西洋 。
 *
 * 示例 1：
 *
 * 输入: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
 * 输出: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
 * 示例 2：
 *
 * 输入: heights = [[2,1],[1,2]]
 * 输出: [[0,0],[0,1],[1,0],[1,1]]
 *
 * 提示：
 *
 * m == heights.length
 * n == heights[r].length
 * 1 <= m, n <= 200
 * 0 <= heights[r][c] <= 105
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/pacific-atlantic-water-flow
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0417 {

    @Test
    public void test01(){
        //[[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
        int[][] heights = new int[][] {{1,2,2,3,5},{3,2,3,4,4},{2,4,5,3,1},{6,7,1,4,5},{5,1,1,2,4}};
        //[[0,0],[0,1],[1,0],[1,1]]
        //int[][] heights = new int[][] {{2,1},{1,2}};
        List<List<Integer>> lists = new Solution().pacificAtlantic(heights);
        System.out.println(lists.toString());
    }

}
//不断进行判断，使用DFS或者BFS算法进行计算
class Solution {
    List<List<Integer>> lists = new ArrayList<>();
    int[][] arrs;
    int m, n;
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        arrs = heights;
        m = heights.length;
        n = heights[0].length;
        boolean[][] b1 = new boolean[m][n], b2 = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0) {
                    if (!b1[i][j]) {
                        dfs(i, j, b1);
                    }
                }
                if (i == m - 1 || j == n - 1) {
                    if (!b2[i][j]) {
                        dfs(i, j, b2);
                    }
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (b1[i][j] && b2[i][j]) {
                    List<Integer> integers = new ArrayList<>();
                    integers.add(i);
                    integers.add(j);
                    lists.add(integers);
                }
            }
        }
        return lists;
    }

    int[][] dirs = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    public void dfs(int i, int j, boolean[][] b) {
        b[i][j] = true;
        for (int[] dir : dirs) {
            int diri = i + dir[0], dirj = j + dir[1];
            if (diri < 0 || diri >= m || dirj < 0 || dirj >= n) {
                continue;
            }
            if (b[diri][dirj] || arrs[diri][dirj] < arrs[i][j]) {
                continue;
            }
            dfs(diri, dirj, b);
        }
    }
}

//class Solution {
//    int n, m;
//    int[][] g;
//    public List<List<Integer>> pacificAtlantic(int[][] heights) {
//        g = heights;
//        m = g.length; n = g[0].length;
//        //res1代表着太平洋是否能流到该位置，res2代表大西洋
//        boolean[][] res1 = new boolean[m][n], res2 = new boolean[m][n];
//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                //如果当前节点紧贴着上左两边，则一定能流进太平洋
//                //从太平洋开始进行流动
//                if (i == 0 || j == 0) {
//                    if (!res1[i][j]) {
//                        dfs(i, j, res1);
//                    }
//                }
//                //如果当前节点紧贴着下右两边，则一定能流进大西洋
//                //从大西洋开始进行流动
//                if (i == m - 1 || j == n - 1) {
//                    if (!res2[i][j]) {
//                        dfs(i, j, res2);
//                    }
//                }
//            }
//        }
//        //将太平洋和大西洋流到的同一个位置添加进集合，代表能同时流进太平洋和大西洋
//        List<List<Integer>> ans = new ArrayList<>();
//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                if (res1[i][j] && res2[i][j]) {
//                    List<Integer> list = new ArrayList<>();
//                    list.add(i); list.add(j);
//                    ans.add(list);
//                }
//            }
//        }
//        return ans;
//    }
//    //代表着可以向4个方向流动右左下上
//    int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
//    void dfs(int x, int y, boolean[][] res) {
//        //x，y这个坐标一定可以一定可以流入某一个海洋
//        res[x][y] = true;
//        //判断4个方向是否可以进行流动
//        for (int[] di : dirs) {
//            int nx = x + di[0], ny = y + di[1];
//            //左边无法走了/右边无法走了/上面无法走了，下面无法走了
//            if (nx < 0 || nx >= m || ny < 0 || ny >= n) {
//                continue;
//            }
//            //之前已经流过了的地方为true；x，y坐标的高度大于上下左右四个方面时为true，代表水流不进去
//            if (res[nx][ny] || g[nx][ny] < g[x][y]) {
//                continue;
//            }
//            //否则继续向四个方面流
//            dfs(nx, ny, res);
//        }
//    }
//}

//class Solution {
//    int n, m;
//    int[][] g;
//    public List<List<Integer>> pacificAtlantic(int[][] heights) {
//        g = heights;
//        m = g.length; n = g[0].length;
//        Deque<int[]> d1 = new ArrayDeque<>(), d2 = new ArrayDeque<>();
//        //res1代表着太平洋是否能流到该位置，res2代表大西洋
//        boolean[][] res1 = new boolean[m][n], res2 = new boolean[m][n];
//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                if (i == 0 || j == 0) {
//                    //如果当前节点紧贴着上左两边，则一定能流进太平洋
//                    res1[i][j] = true;
//                    d1.addLast(new int[]{i, j});
//                }
//                if (i == m - 1 || j == n - 1) {
//                    //如果当前节点紧贴着下右两边，则一定能流进大西洋
//                    res2[i][j] = true;
//                    d2.addLast(new int[]{i, j});
//                }
//            }
//        }
//        bfs(d1, res1); bfs(d2, res2);
//        List<List<Integer>> ans = new ArrayList<>();
//        //将太平洋和大西洋流到的同一个位置添加进集合，代表能同时流进太平洋和大西洋
//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                if (res1[i][j] && res2[i][j]) {
//                    List<Integer> list = new ArrayList<>();
//                    list.add(i); list.add(j);
//                    ans.add(list);
//                }
//            }
//        }
//        return ans;
//    }
//    int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
//    void bfs(Deque<int[]> d, boolean[][] res) {
//        while (!d.isEmpty()) {
//            int[] info = d.pollFirst();
//            int x = info[0], y = info[1], t = g[x][y];
//            for (int[] di : dirs) {
//                int nx = x + di[0], ny = y + di[1];
//                if (nx < 0 || nx >= m || ny < 0 || ny >= n) {
//                    continue;
//                }
//                if (res[nx][ny] || g[nx][ny] < t) {
//                    continue;
//                }
//                d.addLast(new int[]{nx, ny});
//                res[nx][ny] = true;
//            }
//        }
//    }
//}

//class Solution {
//    List<List<Integer>> lists = new ArrayList<>();
//    int[][] arrs;
//    int m, n;
//    public List<List<Integer>> pacificAtlantic(int[][] heights) {
//        //什么叫做流进了太平洋，当x = 0时，或者当y = 0时，代表流进了太平洋
//        //什么叫做流进了大西洋，当x = n时，或者当y = m时，代表流进了太平洋
//        //水流走直线
//        arrs = heights;
//        m = heights.length;
//        n = heights[0].length;
//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j < m; j++) {
//                //判断是否满足条件，满足则添加一个list
//                if (isPacificAndAtlantic(i ,j)) {
//                    List<Integer> integers = new ArrayList<>();
//                    integers.add(i);
//                    integers.add(j);
//                    lists.add(integers);
//                }
//            }
//        }
//        return lists;
//    }
//
//    public boolean isPacificAndAtlantic(int i, int j) {
//        //如果当前坐标，假设x轴不变，y轴慢慢变小的情况下，值不断变小，或y轴不变，x轴慢慢变小的情况下，值不断变小，都可以认定是可以流进太平洋
//        //能否到达太平洋，upFlag和leftFlag其中一个为true则可以到达
//        boolean upFlag = true;
//        boolean leftFlag = true;
//        //能否到达太平洋，downFlag和rightFlag其中一个为true则可以到达
//        boolean downFlag = true;
//        boolean rightFlag = true;
//        for (int y = j; y > 0; y--) {
//            //当前坐标比上面一个大
//            int i1 = arrs[i][y];
//            if (i1 < arrs[i][y - 1]) {
//                upFlag = false;
//                break;
//            }
//        }
//        if (!upFlag) {
//            for (int x = i; x > 0; x--) {
//                //当前坐标比左边一个大
//                int i1 = arrs[x][j];
//                if (i1 < arrs[x - 1][j]) {
//                    leftFlag = false;
//                    break;
//                }
//            }
//        }
//
//        for (int y = j; y < m - 1; y++) {
//            //当前坐标比下面一个大
//            int i1 = arrs[i][y];
//            if (i1 < arrs[i][y + 1]) {
//                downFlag = false;
//                break;
//            }
//        }
//        if (!downFlag) {
//            for (int x = i; x < n - 1; x++) {
//                //当前坐标比右边一个大
//                int i1 = arrs[x][j];
//                if (i1 < arrs[x + 1][j]) {
//                    rightFlag = false;
//                    break;
//                }
//            }
//        }
//
//        return (upFlag || leftFlag) && (downFlag|| rightFlag);
//    }
//}

//class Solution {
//    int n, m;
//    int[][] g;
//    public List<List<Integer>> pacificAtlantic(int[][] heights) {
//        g = heights;
//        m = g.length; n = g[0].length;
//        Deque<int[]> d1 = new ArrayDeque<>(), d2 = new ArrayDeque<>();
//        boolean[][] res1 = new boolean[m][n], res2 = new boolean[m][n];
//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                if (i == 0 || j == 0) {
//                    res1[i][j] = true;
//                    d1.addLast(new int[]{i, j});
//                }
//                if (i == m - 1 || j == n - 1) {
//                    res2[i][j] = true;
//                    d2.addLast(new int[]{i, j});
//                }
//            }
//        }
//        bfs(d1, res1); bfs(d2, res2);
//        List<List<Integer>> ans = new ArrayList<>();
//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                if (res1[i][j] && res2[i][j]) {
//                    List<Integer> list = new ArrayList<>();
//                    list.add(i); list.add(j);
//                    ans.add(list);
//                }
//            }
//        }
//        return ans;
//    }
//    int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
//    void bfs(Deque<int[]> d, boolean[][] res) {
//        while (!d.isEmpty()) {
//            int[] info = d.pollFirst();
//            int x = info[0], y = info[1], t = g[x][y];
//            for (int[] di : dirs) {
//                int nx = x + di[0], ny = y + di[1];
//                if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
//                if (res[nx][ny] || g[nx][ny] < t) continue;
//                d.addLast(new int[]{nx, ny});
//                res[nx][ny] = true;
//            }
//        }
//    }
//}
//
//作者：AC_OIer
//链接：https://leetcode-cn.com/problems/pacific-atlantic-water-flow/solution/by-ac_oier-do7d/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

//class Solution {
//    int n, m;
//    int[][] g;
//    public List<List<Integer>> pacificAtlantic(int[][] heights) {
//        g = heights;
//        m = g.length; n = g[0].length;
//        boolean[][] res1 = new boolean[m][n], res2 = new boolean[m][n];
//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                if (i == 0 || j == 0) {
//                    if (!res1[i][j]) dfs(i, j, res1);
//                }
//                if (i == m - 1 || j == n - 1) {
//                    if (!res2[i][j]) dfs(i, j, res2);
//                }
//            }
//        }
//        List<List<Integer>> ans = new ArrayList<>();
//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                if (res1[i][j] && res2[i][j]) {
//                    List<Integer> list = new ArrayList<>();
//                    list.add(i); list.add(j);
//                    ans.add(list);
//                }
//            }
//        }
//        return ans;
//    }
//    int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
//    void dfs(int x, int y, boolean[][] res) {
//        res[x][y] = true;
//        for (int[] di : dirs) {
//            int nx = x + di[0], ny = y + di[1];
//            if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
//            if (res[nx][ny] || g[nx][ny] < g[x][y]) continue;
//            dfs(nx, ny, res);
//        }
//    }
//}
//
//作者：AC_OIer
//链接：https://leetcode-cn.com/problems/pacific-atlantic-water-flow/solution/by-ac_oier-do7d/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

//基本分析
//整理题意，需要我们统计能够同时流向两片海域的格子。
//从源点（格子）流向汇点（海域）是按照高度从高到低（非严格）的规则，
//那么反过来从海域到格子则是按照从低到高（非严格）规则进行，
//同时本身处于边缘的格子与海域联通。
//因此我们可以使用两遍 DFS/BFS 进行求解：
//分别从与当前海域直接相连的边缘格子出发，
//统计能够流向当前海域的格子集合，两片海域求得的集合交集即是答案。
//BFS（多源 BFS）
//使用 BFS 进行求解：
//目的是构造出两个答案矩阵 res_1 ​和 res_2，
//res_k[i][j] = true 代表格子 (i, j) 能够流向海域，
//起始将所有与海域相连的格子放入队列，然后跑一遍 BFS ，
//所有能够进入队列的格子均能够与海域联通。
//最后统计所有满足 res_1[i][j] = res_2[i][j] = true 的格子即是答案。
//
//作者：AC_OIer
//链接：https://leetcode-cn.com/problems/pacific-atlantic-water-flow/solution/by-ac_oier-do7d/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
